package class006;

import java.util.Arrays;

// 有序数组中找>=num的最左位置
public class  Code02_FindLeft {



	// 为了验证
	public static int[] randomArray(int n, int v) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = (int) (Math.random() * v) + 1;
		}
		return arr;
	}

	// 为了验证
	// 保证arr有序，才能用这个方法
	public static int right(int[] arr, int num) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] >= num) {
				return i;
			}
		}
		return -1;
	}

	// 保证arr有序，才能用这个方法
	// 有序数组中找>=num的最左位置
	public static int findLeft(int[] arr, int num) {
		int l = 0, r = arr.length - 1, m = 0;
		int ans = -1;
		while (l <= r) {
			// m = (l + r) / 2;
			// m = l + (r - l) / 2;
			m = l + ((r - l) >> 1);
			if (arr[m] >= num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}


	/**
	 * 保证arr有序
	 * 有序数组中找 == num 的最左位置
	 * @param arr
	 * @param num
	 * @return
	 */
	public static int findLeftEqeNum(int[] arr, int num) {
		int l = 0, r = arr.length - 1, m = 0;
		int ans = -1;
		while (l <= r) {
			// m = (l + r) / 2;
			// m = l + (r - l) / 2;
			m = l + ((r - l) >> 1);
			if (arr[m] >= num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return arr[ans] == num ? ans : -1;
	}


	// 为了验证
	public static void main(String[] args) {
		int[] arr= {1,3,4,4,4,12,17,17,21};
		int leftNum = findLeft(arr,16);
		int leftEqeNum = findLeftEqeNum(arr, 16);
		System.out.println(leftNum);
		System.out.println(leftEqeNum);


	}





}
